# Ленивые вычисления

Нестрогость (или ленивое вычисление) — это свойство функции. 
Сказать, что функция не является строгой, просто означает, 
что функция может решить не оценивать один или несколько своих аргументов. 
Напротив, строгая функция всегда оценивает свои аргументы. 
Строгие функции являются нормой в большинстве языков программирования. 
Если не указано иное, любое определение функции в Scala будет строгим. 

В качестве примера рассмотрим следующую функцию:

```dotty
def square(x: Double): Double = x * x
```

При вызове `square(41.0 + 1.0)`, функция `square` получит оценочное значение `42.0`, потому что она строгая.
Напротив, сокращающие логические функции `&&` и `||`, 
встречающиеся во многих языках программирования, включая Scala, не являются строгими.
Функция `&&` принимает два логических аргумента, но оценивает второй аргумент только в том случае, если первый истинен:

```dotty
false && { println("!!"); true }
// res0: Boolean = false
```

Аналогично `||` оценивает свой второй аргумент, только если первый `false`:

```dotty
true || { println("!!"); false }
// res1: Boolean = true
```

Еще одним примером нестрогости является управляющая конструкция `if` в Scala:

```dotty
val result = if input.isEmpty then sys.error("empty input") else input
```

Нестрогие вычисления не кэшируются и вычисляются каждый раз при вызове:

```dotty
def maybeTwice(b: Boolean, i: => Int) = if b then i + i else 0
val x = maybeTwice(true, { println("hi"); 1 + 41 })
// hi
// hi
// x: Int = 84
```

## Lazy List

Рассмотрим, как можно использовать нестрогость для повышения эффективности 
и модульности функциональных программ на примере ленивых списков. 
Цепочки преобразований в ленивых списках объединяются в один проход благодаря использованию нестрогости. 
Вот простое определение `LazyList`:

```dotty
enum LazyList[+A]:
  case Empty
  case Cons(h: () => A, t: () => LazyList[A])

import LazyList.*

object LazyList:
  def cons[A](hd: => A, tl: => LazyList[A]): LazyList[A] =
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)

  def empty[A]: LazyList[A] = Empty

  def apply[A](as: A*): LazyList[A] =
    if as.isEmpty then empty
    else cons(as.head, apply(as.tail*))
```

С помощью `LazyList` можно построить вычисление, которое производит последовательность элементов, 
не выполняя шаги этого вычисления до тех пор, пока эти элементы действительно не понадобятся. 
Вообще говоря, нестрогость позволяет отделить описание выражения от вычисления этого выражения. 
Это дает мощную возможность — можно описать «бОльшее» выражение, чем нужно, а затем вычислить только его часть.

В качестве примера может служить функция `exists`, 
которая проверяет, существует ли в `LazyList` элемент, соответствующий логической функции:

```dotty
def exists(p: A => Boolean): Boolean = this match
  case Cons(h, t) => p(h()) || t().exists(p)
  case _ => false
```

`||` не является строгим по второму аргументу, а значит если `p(h())` возвращает `true`, 
то `exists` завершает обход досрочно и также возвращает `true`. 
Заметим, что конец `LazyList` — это lazy val. 
Таким образом, обход не только раньше завершается, но и остаток `LazyList` вообще никогда не оценивается! 
Таким образом, любой код, который сгенерировал бы остаток, на самом деле никогда не выполняется.

Аналогично с реализациями других методов: эти реализации являются инкрементными — они не полностью генерируют свои ответы. 
Только после того, как какое-то другое вычисление просмотрит элементы результирующего `LazyList`, 
вычисление для создания этого `LazyList` действительно не произойдет, 
и тогда оно выполнит ровно столько работы, сколько нужно для создания запрошенных элементов. 
Из-за этого инкрементного характера можно вызывать эти функции 
одну за другой без полного создания промежуточных результатов. 

Инкрементальный характер ленивых преобразований списка также имеет важные последствия для использования памяти. 
Поскольку промежуточные ленивые списки не генерируются, 
преобразование ленивого списка требует ровно столько рабочей памяти, 
сколько необходимо для хранения и преобразования текущего элемента.

## Бесконечные ленивые списки 

Поскольку преобразования являются инкрементальными, написанные функции также работают с бесконечными `LazyList`. 
Вот пример бесконечного `LazyList` из единиц:

```dotty
val ones: LazyList[Int] = LazyList.cons(1, ones)
ones.take(5).toList
// res2: List[Int] = List(1, 1, 1, 1, 1)
ones.exists(_ % 2 != 0)
// res3: Boolean = true
```

## Корекурсия

Рассмотрим функцию `unfold`:

```dotty
def unfold[A, S](state: S)(f: S => Option[(A, S)]): LazyList[A] = f(state) match
  case None         => Empty
  case Some((a, s)) => Cons(() => a, () => unfold(s)(f))       
```

Функция `unfold` является примером того, что иногда называют корекурсивной функцией. 
В то время как рекурсивная функция потребляет данные, корекурсивная функция их производит. 
И в то время как рекурсивные функции завершаются рекурсией на меньших входных данных, 
корекурсивные функции не должны завершаться, пока они остаются продуктивными, 
что означает, что всегда можно оценить больше результата за конечное время. 
Функция развертывания продуктивна до тех пор, пока `f` завершается, 
поскольку нужно просто запустить функцию `f` еще раз, чтобы сгенерировать следующий элемент `LazyList`. 
Корекурсию также иногда называют защищенной рекурсией, а производительность также иногда называют котерминацией.

## Резюме 

- Нестрогость — полезный метод, который позволяет разделить задачи и улучшить модульность. 
- Отделение описания вычисления от его выполнения предоставляет возможности 
  для повторного использования и повышения эффективности.


---

**Ссылки:**

- [Functional Programming in Scala, Second Edition, Chapter 5](https://www.manning.com/books/functional-programming-in-scala-second-edition?query=Functional%20Programming%20in%20Scala,%20Second%20Edition)
